#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;

void MakeHeap(int* array, int num, int size)
{
    int t = array[num];
    int j = 2 * num + 1;
    
    while (j < size)
    {
        if (j + 1 < size && array[j] > array[j + 1])
        {
            j++;
        }
        
        if (t > array[j])
        {
            array[num] = array[j];
            num = j;
            j = 2 * j + 1;
        }
        else
        {
            break;
        }
    }
    
    array[num] = t;
}

void HeapSort(int* array, int size)
{
    for (int i = (size - 2) / 2; i >= 0; --i)
    {
        MakeHeap(array, i, size);
    }
    
    for (int i = 0; i < size - 1; ++i)
    {
        cout<< array[0] << " ";
        array[0] = array[size - 1 - i];
        MakeHeap(array, 0, size - 1 - i);
    }
}

int main(void)
{
    int array[] = {52, 49, 80, 36, 14, 58, 61, 23, 97, 75};
    int size = sizeof(array) / sizeof(array[0]);
    
    HeapSort(array, size);
    
    system("pause");
}
